package day04;

/**
 * @author aiPlusPlus
 * @version 1.0
 * @date 2023/2/4 22:36
 */

import java.util.HashSet;
import java.util.Set;

/**
 * 给你一个整数数组 banned 和两个整数 n 和 maxSum 。你需要按照以下规则选择一些整数：
 *
 * 被选择整数的范围是 [1, n] 。
 * 每个整数 至多 选择 一次 。
 * 被选择整数不能在数组 banned 中。
 * 被选择整数的和不超过 maxSum 。
 * 请你返回按照上述规则 最多 可以选择的整数数目。
 *
 *
 *
 * 示例 1：
 *
 * 输入：banned = [1,6,5], n = 5, maxSum = 6
 * 输出：2
 * 解释：你可以选择整数 2 和 4 。
 * 2 和 4 在范围 [1, 5] 内，且它们都不在 banned 中，它们的和是 6 ，没有超过 maxSum 。
 * 示例 2：
 *
 * 输入：banned = [1,2,3,4,5,6,7], n = 8, maxSum = 1
 * 输出：0
 * 解释：按照上述规则无法选择任何整数。
 * 示例 3：
 *
 * 输入：banned = [11], n = 7, maxSum = 50
 * 输出：7
 * 解释：你可以选择整数 1, 2, 3, 4, 5, 6 和 7 。
 * 它们都在范围 [1, 7] 中，且都没出现在 banned 中，它们的和是 28 ，没有超过 maxSum 。
 */
public class Solution10 {
    public int maxCount(int[] banned, int n, int maxSum) {
        Set<Integer> hs = new HashSet<>();
        for (int i : banned) {
            hs.add(i);
        }
        int count = 0;
        int num = 0;
        for (int i = 1; i <= n; i++) {
            if(!hs.contains(i)){
                if(num+i<=maxSum){
                    num+=i;
                    count++;
                }else {
                    return count;
                }
            }
        }
        return count;
    }
}
